/**********************************************************
                     sparse.c
this is a sparse matrix (not the Sparse Clam function).
written by CAS
***********************************************************/
#include <stdio.h>
#include <malloc.h>
#include "clam.h"

extern void CTG_resources();
static ZINSTANCE *II = NULL;

static void all_ok(i1, i2)
int i1, i2;
{
    if (II == NULL) {
	fprintf(stderr,"No II\n");
	exit(0);
    }
    if (II->pool == NULL) {
	fprintf(stderr,"No active II\n");
	exit(0);
    }
    if (i1<0 || i1 >= II->size)  {
	fprintf(stderr,"Ztravers i1 (%d) is greater than max size (%d)\n",
						i1,II->size);
	exit(0);
    }
    if (i2<0 || i2 >= II->size)  {
	fprintf(stderr,"Ztravers i2 (%d) is greater than max size (%d)\n",
						i2,II->size);
	exit(0);
    }
}
/**************************************************************
                   DEF: Zcreate_instance
**************************************************************/
int Zcreate_instance(name, I, size)
char *name;
ZINSTANCE *I;
int size;
{
int i;

/* the size may change in zap.c if not all clones used */

    if (size == 0) {
	fprintf(stderr,"No size\n");
	return 0;
    }
    if (II!=NULL && II == I && strcmp(name, II->name)==0)
    {  printf("Sparse matrix already exists for %s\n",II->name); 
       Zdestroy_instance(I);
    }
    if (I->max != 0) Zdestroy_instance(I);

    I->size = size;
    I->matrix = (ZMATRIX *) calloc(size, sizeof(ZMATRIX));
    NOMEM3(I->matrix, "ZMATRIX", 0);
    for (i=0; i< size; i++) {
         I->matrix[i].cin = -1; 
         I->matrix[i].first = -1; 

         pthread_mutex_init(&I->matrix[i].lock, 0);

    }
    
    pthread_mutex_init(&I->lock, 0);

    I->max = size * 12;
    I->pool = (ZNODE *) calloc(I->max, sizeof(ZNODE));
    NOMEM3(I->pool, "ZNODE", 0);
    I->num = 0;
    strcpy(I->name ,name);
    II = I;
return 1;
}
/**************************************************************
                   DEF: Zactiviate_instance
**************************************************************/
void Zactivate_instance(I)
ZINSTANCE *I;
{
    II = I;
}
/**************************************************************
                   DEF: Zdestroy_instance
**************************************************************/
void Zdestroy_instance(I)
ZINSTANCE *I;
{
	int i;
	for (i = 0; i < I->size; i++) pthread_mutex_destroy(&I->matrix[i].lock);
	pthread_mutex_destroy(&I->lock);
	
    if (I == NULL) return;
    if (II == I) II = NULL;
    if (I->matrix != NULL) free(I->matrix);
    if (I->pool != NULL) free(I->pool);
    I->matrix = NULL;
    I->pool = NULL;
    I->size = I->num = I->max = 0;
    I->name[0] = '\0';
}
/***************************************************************
		   DEF: Znew_node
***************************************************************/
ZNODE  *Znew_node(i1, i2)
  int i1,i2;
{
  ZNODE  *node;
  int i,j,k, num, first;
	
  all_ok(i1, i2);
  
  pthread_mutex_lock(&II->matrix[i1].lock);


  if ((node = Zif_exist(i1, i2)))
	{
	  if (Ztrace == 2) printf("already exist %d %d\n",i1, i2);


	  pthread_mutex_unlock(&II->matrix[i1].lock);
	  return node;
	}
	
  first = II->matrix[i1].first;

  pthread_mutex_lock(&II->lock);
  
  if (II->num == II->max)
	{

      /* This should be ok b/c in no other place does a single thread
       * possess more than one mutex. So we can hold them all.
       */
	  for (j = 0; j < ZZ.size; j++)
		{
		  if (j != i1) pthread_mutex_lock(&II->matrix[j].lock);
		}
		

	j = MiN(i1,i2);
	num = II->size - j; /* number left to process */
	i = (II->max/j);  /* 2x avg overlap */    
	k = num*i;    

	II->max += k;
	II->pool = (ZNODE *) realloc(II->pool, (II->max * sizeof(ZNODE)));
	if (II->pool==NULL) {
	  fprintf(stdout,"Memory allocation: %d increase %d at #%d\n", 
			  II->max, k,j);
	  fprintf(stderr,"\n**Memory allocation error: Max %d (%d bytes)\n", 
			  II->max, II->max*sizeof(ZNODE));
	  CTG_resources();
	  exit(0);
         }

	for (j = 0; j < ZZ.size; j++)
	  {
		if (j != i1)  pthread_mutex_unlock(&II->matrix[j].lock);
	  }
	}
	
  num = II->num;
  II->num++;

  pthread_mutex_unlock(&II->lock);
  

  if (first == -1) 
	{  /* row is presently empty, fill first */
	II->matrix[i1].first = num;
	II->pool[num].next = -1;
  }
  else if (II->pool[first].i2 > i2) 
	{  /* This node precedes the first node on the row, insert */
	II->pool[num].next = first;
	II->matrix[i1].first = num;
  }
  else 
	{ 
	  /* Find the place we will be inserting */

	for (first = i = II->matrix[i1].first;
		 II->pool[i].i2 < i2 && II->pool[i].next != -1;
	   first = i, i = II->pool[i].next);

	  /* Does the node already exist? */
	
	/*if (II->pool[i].i2 == i2 && II->pool[i].exponent != -1) */
	if (II->pool[i].i2 == i2)
	  {  /* Yes - report error and return it */
	  printf("This node should not be here %d %d\n",i1, i2);
	  return &(II->pool[i]);
	}
	  /* Have we run off the end? */
	else if (II->pool[i].i2 < i2) 
	  {  /* Yes,  append to list */
	  II->pool[i].next = num;
	  II->pool[num].next = -1;
	}
	else 
	  {  /* No, insert in the middle */
	  II->pool[num].next = II->pool[first].next;
	  II->pool[first].next = num;
	}
  }
  node = &(II->pool[num]);
  node->i1 = i1;
  node->i2 = i2;
  node->exponent = 0;


  /* Done, release lock on this row */
  pthread_mutex_unlock(&II->matrix[i1].lock);

  
  return node;
}
/***************************************************************
		   Zdelete_node
***************************************************************/
void Zdelete_node(i1, i2)
int i1, i2;
{
ZNODE *node;
  if ((node = Zif_exist(i1, i2)))
      node->exponent  = -1;
}
/***********************************************************************
		 Ztraverse
************************************************************************/
static int old_i1= -1, next_i2= -1;

ZNODE *Ztraverse(i1)
int i1;
{
     all_ok(i1, 0);
     if (II->matrix[i1].first == -1) return NULL;

     if (old_i1 != i1 || next_i2 == -1) 
        next_i2 = II->matrix[i1].first;
     else
        next_i2 = II->pool[next_i2].next; 
     old_i1 = i1;
     if (next_i2 == -1) return NULL;
     return &(II->pool[next_i2]);
}
/*******************************************************************
			Zif_node
*********************************************************************/
int  Zif_node(i1)
int i1;
{
   if (i1  >= II->size || II->matrix[i1].first== -1) return 0;
   return 1;
}
/*******************************************************************
			Zif_exist
*********************************************************************/
ZNODE  *Zif_exist(i1, i2)
int i1, i2;
{
int i;

   all_ok(i1, i2);
   if (II->matrix[i1].first== -1) return NULL;

   for (i = II->matrix[i1].first;
      II->pool[i].i2 < i2 && II->pool[i].next != -1;
      i = II->pool[i].next);
   /* if (II->pool[i].i2 == i2 && II->pool[i].exponent != -1) */
      if (II->pool[i].i2 == i2)
           return &(II->pool[i]);
   return NULL;
}
/***********************************************************************/
void Zdump_all()
{
int i;
ZNODE *node;
CLONE clone;

   printf("Sparse %s size %d num %d max %d\n",
            II->name, II->size, II->num, II->max);
   for (i=0; i< II->size; i++)
      if (II->matrix[i].first != -1) {
         clone = arr(acedata, II->matrix[i].cin, CLONE);
         printf("\n%2d: %12s %2d (%d %4d %4d %4d)\n",i, clone.clone, clone.fp->b2, 
                       II->matrix[i].set+1, II->matrix[i].pick, 
                       II->matrix[i].leftb, II->matrix[i].rightb);
         printf(" %d mom %d %d\n", ZZ.matrix[i].grand, 
              ZZ.matrix[i].mtype, ZZ.matrix[i].high_match);
         while ((node = Ztraverse(i))) Zdump_node("Z",node, clone.fp->b2);
      }
}
void Zdump_node(msg, node, size)
char *msg;
ZNODE *node;
{
CLONE clone;
   clone = arr(acedata, II->matrix[node->i2].cin, CLONE);
   printf("%12s: Node %5d  (%2d/%2d) %2d (%d %4d %4d %4d) \n", clone.clone,
          node->i2, size, clone.fp->b2, node->exponent,   
          II->matrix[node->i2].set+1, II->matrix[node->i2].pick,
          II->matrix[node->i2].leftb, II->matrix[node->i2].rightb);
}
void Zdump_matrix(int i)
{
CLONE clone;
ZNODE *node;
   if (II->matrix[i].cin == -1) return;
   clone = arr(acedata, II->matrix[i].cin, CLONE);
   printf("\n%2d: %12s %2d: ",i, clone.clone, clone.fp->b2);
   printf(" %d mtype %d exponent %d (%d %4d %4d %4d)\n", ZZ.matrix[i].grand, 
       ZZ.matrix[i].mtype, ZZ.matrix[i].high_match,
       II->matrix[i].set+1, II->matrix[i].pick, II->matrix[i].leftb, II->matrix[i].rightb);
   if (II->matrix[i].first != -1) 
       while ((node = Ztraverse(i))) Zdump_node("Z",node, clone.fp->b2);
    
}

void Zdump_clhigh()
{
int i;
   for (i=0; i<ZZ.size; i++)
        if (ZZ.matrix[i].cin == clhigh->next) {
            Zdump_matrix(i);
            return;
        }
}

void Zdump_pool(char *msg)
{
int i;
  for (i=0; i<II->num; i++)
   if (II->pool[i].i1 < 0 || II->pool[i].i2 < 0)
      printf("%d %s Pool %d %d %d\n", ZS, msg, i, II->pool[i].i1, II->pool[i].i2);
}
